解题思路

首先问题的意思是，在原始位置互不相邻的条件下，所选硬币的总值最大。设第 i 个硬币币值为 Ci，可选最大金额为 F(i)。

现在我们来考虑一般情况，对于每个硬币 i 我们有两种选择：要<--or-->不要 要 i ：那么可选硬币的金额 F( i ) = F( i - 2 ) + Ci ； 不要 i ：那么可选硬币的金额 F( i ) = F( i - 1 ) ； 此时我们就得到了递推方程： F（n）= max{ F（n - 2）+ Ci ， F（n - 1）}

现在我们考虑一下退出条件（特殊情况）： 当 n = 0 时，有 F（0）= 0； 当 n = 1 时，有 F（1）= C1； 这样就构建一个递归函数解题。

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int arr[10005];

int Max(int a, int b)                    //求最大值
{
    return a > b ? a : b;
}

void MaxValue(int n)
{
    arr[n] = Max(arr[n - 1], arr[n - 2] + arr[n]);
}

int main()
{
    memset(arr, 0, sizeof(arr));
    int n;
    scanf("%d", &n);
    for (int i = 1; i < n + 1; i++)
        scanf("%d", &arr[i]);

    for (int i = 2; i < n + 1; i++)    //从头开始找出每 i 个硬币的最大金额值
        MaxValue(i);

    printf("%d\r\n",arr[n]);

    return 0;
}